//
// Created by Administrator on 2022/11/16.
// 分大于等于小于区 以最后一个数字为准
//

#include <iostream>
#include <vector>
#include "arrUtil.h"
using namespace std;

int netherlands(vector<int> &v,int l, int r)
{
    if (l==r)
        return l;
    int small=l-1;
    int big=r;
    int cur = v[r];
    int i=l;
    while (i<big)
    {
        if (v[i]<cur)
        {
            swapVector(v,++small,i);
            i++;
        }else if(v[i]>cur)
        {
            swapVector(v,--big,i);
        }else{
            i++;
        }
    }
//    printf("\nsmall:%d big:%d\n",small,big);
    printf("i:%d, r-1: %d\n",i,r-1 );
//    printf("i-1: %d\n",i-1 );
    swapVector(v,big,r);
    return i;
}

void quickSort(vector<int> &a,int l,int r)
{
    if (l<r)
    {
        int mid = netherlands(a,l,r);
        netherlands(a,l,mid-1);
        netherlands(a,mid+1,r);
    }

}

int main()
{
    vector<int> arr={7,2,9,3,6,3,6,5,4};
//    arr={7,6,5,9,6};
//    arr={5,6};
//    arr={2,3,3};
//    arr={2,3};
//    arr={2};
//    netherlands(arr,0,arr.size()-1);
//    printVector(arr);
//    randVector(arr,10);
    quickSort(arr,0,arr.size()-1);
    printVector(arr);
    return 0;
}
